package com.leetcode.程序员面试金典.medium;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 覃国强
 * @date 2021-04-10 19:10
 */
public class 面试题_17_13_恢复空格 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    String[] dictionary = {"sssjjs", "hschjf", "hhh", "fhjchfcfshhfjhs", "sfh", "jsf",
        "cjschjfscscscsfjcjfcfcfh", "hccccjjfchcffjjshccsjscsc", "chcfjcsshjj", "jh", "h", "f", "s",
        "jcshs", "jfjssjhsscfc"};
    String sentence = "sssjjssfshscfjjshsjjsjchffffs";
    int respace = solution.respace(dictionary, sentence);
    System.out.println(respace);
  }

  static
  class Solution {

    public int respace(String[] dictionary, String sentence) {
      if (sentence == null || sentence.length() == 0) {
        return 0;
      }
      if (dictionary == null || dictionary.length == 0) {
        return sentence.length();
      }
      TrieNode root = TrieNode.generateReverseOrderTrieTree(dictionary);
      char[] chars = sentence.toCharArray();
      int[] dp = new int[sentence.length() + 1];
      dp[0] = 0;

      for (int i = 1; i < dp.length; ++i) {
        dp[i] = dp[i - 1] + 1;
        int j = i;
        TrieNode tmp = root;
        while (j > 0 && tmp.children.containsKey(chars[j - 1])) {
          tmp = tmp.children.get(chars[j - 1]);
          if (tmp.isFinal) {
            dp[i] = Math.min(dp[i], dp[j - 1]);
          }
          --j;
        }
      }
      return dp[sentence.length()];
    }

    static class TrieNode {

      Map<Character, TrieNode> children = new HashMap<>();

      boolean isFinal;

      public static TrieNode generateReverseOrderTrieTree(String[] dictionary) {
        TrieNode root = new TrieNode();
        for (String word : dictionary) {
          TrieNode tmp = root;
          char[] chars = word.toCharArray();
          for (int i = chars.length - 1; i >= 0; --i) {
            if (!tmp.children.containsKey(chars[i])) {
              tmp.children.put(chars[i], new TrieNode());
            }
            tmp = tmp.children.get(chars[i]);
          }
          tmp.isFinal = true;
        }
        return root;
      }
    }
  }

}
